﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ProgramTest
{
    public static class AlgorithmShow
    {  
        public static void Show()
        {
            //Reverse2();
            //Mu();
            //Print(1);
            //string[] arr = "".Split(',');
            //int a;
            //int.TryParse("1", out a);

            ////约瑟夫环数组求解
            //string result = Josephus("50,3");

            //YueSeFuHuan(50, 3);

            string reult = string.Empty;
            GetNumber2("aaabbcccaab");

        }

        /// <summary>
        /// 求连续不重复字符的个数
        /// </summary>
        /// <param name="strSource"></param>
        public static void GetNumber2(string strSource)
        {
            List<TempItem> tempItems = new List<TempItem>();
            for (int i = 0; i < strSource.Length; i++)
            {
                char c = strSource[i];
                var items = tempItems.Where(x => x.k == c);
                if (items.Count() == 0)
                {
                    tempItems.Add(new TempItem()
                    {
                        k = c,
                        c = 1,
                        i = 1
                    });
                }
                else
                {
                    var item = tempItems.Last();
                    if (item.k == c)
                    {
                        item.c = item.c + 1;
                    }
                    else
                    {
                        tempItems.Add(new TempItem()
                        {
                            k = c,
                            c = 1,
                            i = items.Last().i + 1
                        });
                    }
                }

            }
        }


        //从第start人开始计数，以alter为单位循环记数出列，总人数为total 
        public static int[] Jose(int total, int start, int alter)
        {
            int j, k = 0;
            //count数组存储按出列顺序的数据，以当结果返回 
            int[] count = new int[total + 1];
            //s数组存储初始数据 
            int[] s = new int[total + 1];
            //对数组s赋初值,第一个人序号为0,第二人为1，依此下去
            for (int i = 0; i < total; i++)
            {
                s[i] = i;
            }
            //按出列次序依次存于数组count中 
            for (int i = total; i >= 2; i--)
            {
                start = (start + alter - 1) % i;
                if (start == 0)
                    start = i;
                count[k] = s[start];
                k++;
                for (j = start + 1; j <= i; j++)
                    s[j - 1] = s[j];
            }
            count[k] = s[1];
            //结果返回 
            return count;
        }

        public static int GetNumber(string strSource, out string result)
        {
            char[] s = strSource.ToCharArray();
            result = "";
            int count = 0;
            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] >= 48 && s[i] <= 57)
                {
                    count++;
                    result += s[i].ToString();
                }
            }
            return count; ;
        }


        public static void Fun2(string str)
        {
            int[] letters = new int[26]; // 用于保存字符出现的数量 

            for (int i = 0; i < 26; i++) letters[i] = new int();

            str = "aaabbcccaab"; // 读入一行字符串

            Dictionary<char, int> dic = new Dictionary<char, int>();

            for (int i = 0; i < str.Length; i++)
            {

                if (dic.ContainsKey(str[i]))
                {
                    dic[str[i]] += 1;
                }
                else
                {
                    dic.Add(str[i], 1);
                }

            }

            // 打印结果 
            StringBuilder builder = new StringBuilder();
            foreach (var item in dic.Keys)
            {
                builder.Append(dic[item]);
                builder.Append(item);
            }
            string result = builder.ToString();
        }

        /*入口函数，不能删除，因为在下方有调用*/
        static string Josephus(string str)
        {
            string result = string.Empty;
            string[] arr = str.Split(',');
            if (arr.Length == 2)
            {
                int iStartNum = 1, iOutIdx = 0, iTotalNum = 0;
                bool isNum = int.TryParse(arr[0], out iTotalNum) && int.TryParse(arr[1], out iOutIdx);
                if (isNum)
                {
                    List<int> listNum = new List<int>();
                    if (iTotalNum > 0)
                    {
                        for (int i = iStartNum; i <= iTotalNum; i++)
                        {
                            listNum.Add(i);
                        }
                    }
                    List<int> newListNum = Compute(iStartNum, iOutIdx - 1, listNum);
                    result = newListNum[0].ToString();
                }
                else
                    result = "请输入正确的内容！";
            }
            else
                result = "请输入正确的内容！";
            return result;
        }

        /// <summary>
        /// 约瑟夫环问题求解方法
        /// </summary>
        /// <param name="sum">总人数</param>
        /// <param name="num">第几个人出局</param>
        static void YueSeFuHuan(int sum, int num)
        {
            int[] arr = new int[sum];
            for (int i = 0; i < sum; i++)
            {
                arr[i] = 1;
            }

            int count = 0;      //计数器
            int arrlength = arr.Length;  //剩余人数

            while (arrlength > 1)
            {
                for (int i = 0; i < arr.Length; i++)
                {
                    if (arr[i] == 1)
                    {
                        count++;
                        if (count == num)   //如果是规定（第几个人出局）
                        {
                            arr[i] = 0;   //第i个人出局
                            arrlength--;
                            count = 0;
                            Console.WriteLine("第{0}个人出局,编号是{1}", i + 1, i);
                        }
                    }
                }
            }

            for (int i = 0; i < arr.Length; i++)
            {
                if (arr[i] == 1)
                {
                    Console.WriteLine("第{0}个人留下，编号是{1}", i + 1, i);
                }

            }
        }


        private static List<int> Compute(int iStartNum, int iOutIdx, List<int> listNum)
        {
            if (listNum.Count == 1)
            {
                return listNum;
            }
            List<int> newListNum = new List<int>();
            int idx = 0;
            bool isStart = true;
            for (int i = 0; i <= listNum.Count - 1; i++)
            {
                if (i < iOutIdx)
                {
                    if (isStart)
                        newListNum.Add(listNum[i]);
                    else
                    {
                        newListNum.Insert(idx, listNum[i]);
                        idx++;
                    }
                }
                //49，50，1，2
                if (i > iOutIdx)
                {
                    newListNum.Insert(idx, listNum[i]);
                    idx++;
                    if (idx == 1)
                    {
                        iStartNum = listNum[i];
                        isStart = false;
                    }
                }
            }
            if (newListNum.Count - 1 < iOutIdx)
            {
                iOutIdx = iOutIdx % (newListNum.Count);
            }
            return Compute(iStartNum, iOutIdx, newListNum);
        }



        /// <summary>
        /// 不用循环打印 1-200
        /// </summary>
        /// <param name="number"></param>
        /// <returns></returns>
        private static bool Print(int number)
        {
            Console.WriteLine(number);
            return number >= 200 || Print(number + 1);
        }


        public static void Mu()
        {
            string t = string.Empty;
            for (int i = 1; i < 10; i++)
            {
                for (int j = 1; j <= i; j++)
                {
                    t = string.Format("{0}*{1}={2} ", j, i, i * j);
                    Console.Write(t);
                    if (i == j)
                        Console.WriteLine("");
                }
            }
        }


        public static string Reverse()
        {
            string s = "I am a good man";
            string[] arr = s.Split(' ');
            string sResult = string.Empty;
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = arr.Length - 1; i >= 0; i--)
            {
                stringBuilder.Append(arr[i]);
                if (i > 0)
                    stringBuilder.Append(" ");
            }
            sResult = stringBuilder.ToString();
            return sResult;
        }
        public static string Reverse2()
        {
            string s = "I am a good man";
            string[] arr = s.Split(' ');
            Array.Reverse(arr);
            string sResult = string.Empty;
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = arr.Length - 1; i >= 0; i--)
            {
                stringBuilder.Append(arr[i]);
                if (i > 0)
                    stringBuilder.Append(" ");
            }
            sResult = stringBuilder.ToString();
            return sResult;
        }
    }

    public class TempItem
    {
        public char k { get; set; }
        public int c { get; set; }
        public int i { get; set; }
    }
}
